# Roberto Andrino 12413
# Ivan Concua 12352
# FloydWarshall.py
# programa que abre un archivo "grafo.txt" que representa un grafo
# y aplica el algoritmo de Floyd para calcular la distancia mas corta
# entre cualquier par de nodos, y los predecesores.
# El archivo "grafo.txt" debe tener el siguiente formato:
# Cada linea tiene el nombre del primer nodo, el nombre del segundo nodo y el
# peso de ir del primer nodo al segundo.
# Nodo1 Nodo2 Peso

import networkx as nx
g = nx.DiGraph()

# se abre "grafo.txt" y se lee cada linea que tiene.
# Cada linea se separa en el espacio (" ") y se guarda
# en un array. Cada caracter que se agrega al digrafo
# con add_edge.

try:
    grafo = open("grafo.txt")

except:
    print "Error: no se encontro grafo.txt"
    exit()

# lista donde se guardara los caracteres del archivo, y lista donde se guarda los nodos
lineas, nodos = [], [] 

# se lee los caracteres y se agregan a las listas
for line in grafo:
    a = line.strip()
    lineas = a.split(" ")

    # Programacion defensiva que se asegura de que el tercer caracter
    # sea un numero entero
    if(lineas[2].isdigit()):
        g.add_edge(lineas[0], lineas[1], weight = int(lineas[2]))
        nodos.append(lineas[0])
        
    else:
        print "Error: valor invalido en el archivo"
        break

grafo.close()

# se calcula la distancia mas corta y el predecesor por medio del
# metodo de la libreria de networkx. Este metodo usa el algoritmo
# Floyd-Warshall

predecesor, distance = nx.floyd_warshall_predecessor_and_distance(g)
print "distancia mas corta: "
            
# se hace una lista sin caracteres repetidos
noDuplicates = list(set(nodos))
noDuplicates.sort() # se ordena en orden ascendente

#se imprime las distancias mas cortas para cada nodo
i = 0
while i < len(noDuplicates):
    print "Nodo " + noDuplicates[i] + ":"
    print distance[noDuplicates[i]]
    i += 1

print
print "predecesores: "

#se imprime los predecesores para cada nodo
i = 0
while i < len(noDuplicates):
    print "Nodo " + noDuplicates[i] + ":"
    print predecesor[noDuplicates[i]]
    i += 1

